package algorithms.tree;

/**
 * @功能
 * @创建时间 2021/2/2
 */
public class RedBlackBST<Key extends Comparable<Key>,Value> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private Node root;
    private class Node{
        Key key;
        Value val;
        Node left,right;
        int N;
        boolean color;
        Node(Key key,Value val,int N,boolean color){
            this.key=key;
            this.val=val;
            this.N=N;
            this.color=color;
        }
    }

    private boolean isRed(Node x){
        if(x==null) return false;
        return x.color==RED;
    }
    public int size(){
        return size(root);
    }
    private int size(  Node root){
        if(root==null) return 0;
        else return root.N;
    }

    /**
     * 将h变为x的左子节点并将x的左子节点给h，取出变为父节点的h
     * @param h
     * @return
     */
    Node rotateLeft(Node h){
        Node x = h.right;
        h.right=x.left;
        x.left=h;
        x.color=h.color;
        h.color=RED;
        x.N=h.N;
        h.N=1+size(h.left)+size(h.right);
        return x;
    }
    Node rotateRight(Node h){
        Node x=h.left;
        h.left=x.right;
        x.right=h;
        x.color=h.color;
        h.color=RED;
        x.N=h.N;
        h.N=1+size(h.left)+size(h.right);
        return x;
    }
    private void flipColiors(Node h){
        h.color=RED;
        h.left.color=BLACK;
        h.right.color=BLACK;
    }
    public void put(Key key,Value val){
        root=put(root,key,val);
        root.color=BLACK;
        System.out.println(root.key);
        if(root.left!=null)
        System.out.println(root.left.color);
        if(root.right!=null)
        System.out.println(root.right.color);

    }
    private Node put(Node h,Key key,Value val){
        if(h==null) return new Node(key,val,1,RED);
        int cmp=key.compareTo(h.key);
        if(cmp<0) h.left=put(h.left,key,val);
        else if(cmp>0) h.right=put(h.right,key,val);
        else h.val=val;
        if(isRed(h.right)&&!isRed(h.left)) h=rotateLeft(h);
        if(isRed(h.left)&&isRed(h.left.left)) h=rotateRight(h);
        if(isRed(h.left)&&isRed(h.right)) flipColiors(h);
        h.N=size(h.left)+size(h.right)+1;
       // System.out.println(h.color);
        return h;
    }

}
class Client{
    public static void main(String[] args) {
        RedBlackBST a=new RedBlackBST();
        a.put('S',1);
        a.put('E',2);
        a.put('A',3);
        a.put('R',4);
        a.put('C',5);
    }
}
